package club.xiaojiawei.dp;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/8/22 5:55 PM
 * @question 115. 不同的子序列
 * @description 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
 * 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
 */
public class NumDistinct115 {

    public static void main(String[] args) {
        NumDistinct115 test = new NumDistinct115();
        int result = test.numDistinct2("adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc",
                "bcddceeeebecbc");
        System.out.println(result);
    }

    /**
     * 递归回溯-超时
     * @param s
     * @param t
     * @return
     */
    public int numDistinct(String s, String t) {
        if (s.length() < t.length()){
            return 0;
        }
        recursion(s.toCharArray(), 0, t.toCharArray(), 0);
        return count;
    }

    int count = 0;

    public void recursion(char[] sChars, int sIndex, char[] tChars, int tIndex){
        if (tIndex == tChars.length){
            count++;
            return;
        }
        char target = tChars[tIndex];
        for (int i = sIndex; i < sChars.length; i++){
            if (sChars.length - sIndex < tChars.length - tIndex){
                return;
            }else if (target == sChars[i]){
                recursion(sChars, i + 1, tChars, tIndex + 1);
            }
        }
    }

    /**
     * 递归回溯（记忆搜索法）
     * 时间复杂度 O(mn)
     * 空间复杂度 O(mn)
     * @param s
     * @param t
     * @return
     */
    public int numDistinct2(String s, String t) {
        if (s.length() < t.length()){
            return 0;
        }
        this.arr = new int[s.length() + 1][t.length() + 1];
//        -1表示还没遍历到这
        for (int[] ints : arr) {
            Arrays.fill(ints, -1);
        }
        recursion2(s.toCharArray(), 0, t.toCharArray(), 0);
        return arr[0][t.length()];
    }

    /**
     * arr[i][j] = k 表示从s字符串下标i处开始后面的字符串包含t字符串倒数j个字符的可能有k种
     * 所以arr[0][t.length()] 表示结果
     */
    int[][] arr;

    public void recursion2(char[] sChars, int sIndex, char[] tChars, int tIndex){
        if (tIndex == tChars.length){
            arr[sIndex][tChars.length - tIndex] = 1;
            return;
        }
        if (arr[sIndex][tChars.length - tIndex] != -1){
            return;
        }
        char target = tChars[tIndex];
        int amount = 0;
        for (int i = sChars.length - 1; i >= sIndex ; i--){
            if (sChars.length - i >= tChars.length - tIndex && target == sChars[i]){
                recursion2(sChars, i + 1, tChars, tIndex + 1);
                amount = arr[i][tChars.length - tIndex] = arr[i + 1][tChars.length - tIndex - 1] + amount;
            }else {
                arr[i][tChars.length - tIndex] = amount;
            }
        }
    }

    /**
     * 官方-dp
     * 时间复杂度 O(mn)
     * 空间复杂度 O(mn)
     * @param s
     * @param t
     * @return
     */
    public int numDistinct3(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }
        for (int i = m - 1; i >= 0; i--) {
            char sChar = s.charAt(i);
            for (int j = n - 1; j >= 0; j--) {
                char tChar = t.charAt(j);
                if (sChar == tChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }

    /**
     * 民间-递归回溯（记忆搜索法）
     * @param s
     * @param t
     * @return
     */
    public int numDistinct4(String s, String t) {
        int ls = s.length();
        int lt = t.length();
        int[][] arr = new int[ls][lt];
        return cnt(s, t, 0, 0, ls, lt, arr);
    }
    private int cnt(String s, String t, int sIndex, int tIndex, int sL, int tL, int[][] arr){
//        t字符串已经找完
        if(tIndex == tL){
            return 1;
        }
//        s字符串剩下的长度比t字符串剩下的长度小，所以没必要继续下去了，不可能的。
        if(sL - sIndex < tL - tIndex){
            return 0;
        }
        int g = arr[sIndex][tIndex];
        if(g == -1){
//            表示已经搜索过了，且没有符合的
            return 0;
        }else if(g > 0){
//            表示搜索过了，且有符合的，所以直接返回符合的情况个数
            return g;
        }else{
//            表示没有搜索过，所以开始搜索
            int c = 0;
            if(s.charAt(sIndex) == t.charAt(tIndex)){
//                如果字符匹配，则可以继续往后找，并且把后面的可能性个数加上去
                c += cnt(s, t, sIndex + 1, tIndex + 1, sL, tL, arr);
            }
//            加上之前的可能性个数
            c += cnt(s, t, sIndex + 1, tIndex, sL, tL, arr);
//            当前字符搜索完毕，如果可能性个数为0则赋值-1，否则赋值c
            arr[sIndex][tIndex] = c == 0? -1 : c;
//            返回可能性个数
            return c;
        }
    }
}
